1. Field of the Invention
The present invention relates to a prime number generation apparatus for generating prime numbers to be strong public keys in cipher communication, for example, and relates to a B-smoothness judgment apparatus.
2. Description of the Prior Art
In cryptosystem such as a RSA cryptosystem whose security is based on the difficulty of factoring, it is difficult due to computational complexity to obtain prime factors p and q which satisfies n=pq (n is public) in the case where n is about 1024 bits. Moreover, it is a condition of security in cryptography that an attacker cannot obtain p and q from n. Therefore, the security in the cipher communication depends on the quality of the prime numbers p and q to be generated (whether or not they are easily solved into prime factors).
In a conventional method, since prime numbers are generated by using the probable primality test method such as Miller-Rabin, composite numbers which are not prime numbers may be possibly generated in very low probability.
According to "Cryptographic Theory" (written by Eiji Okamoto, published by Kyoritsu Shuppan), etc., in the case where with respect to the prime number p, p-1 or p+1 is the product of only small prime numbers, n can be solved into prime factors comparatively easily by prime factorization algorithm such as a p-1 method or p+1 method. Therefore, in the conventional prime number generating method, a measure is taken to cope with the prime factorization in such a manner that large prime factors p.sub.1 and p.sub.2 are given respectively to p-1 and p+1.
Further, the encryption is repeated u-times so that a cipher text X.sup.e (X: plain text, e: encryption key) of RSA cryptosystem is encrypted into X.sup.e, (X.sup.e).sup.e, ((X.sup.e).sup.e).sup.e, . . . , and thus a plain text X is obtained as represented by the following equation (1). This attack, namely, iterated encryption attack is known. In the conventional prime number generating method, a measure is taken to cope with such an attack in such a manner that a large prime number p.sub.1 ' is included in p.sub.1 -1 as for a large prime factor p.sub.1 included in p-1. EQU X.sup.e.sup..sup.u .ident.X (mod n) (1)
In addition, as a concrete conventional example of the prime number generating method, the following method is known. U.S. Pat. No. 4,633,036 discloses a probable prime number generating method in which p-1 and p+1 respectively include large prime numbers p.sub.1 and p.sub.2, p.sub.1 -1 and p.sub.2 -1 respectively include large prime numbers p.sub.1 ' and p.sub.2 ', and a total bit lengths of p.sub.1 and p.sub.2 cannot exceed a bit length of p. Moreover, Japanese Patent Application Laid-Open 0-73269 (1997) discloses a probable prime number generating method in which p-1 and p+1 respectively include large prime numbers p.sub.1 and p.sub.2, p.sub.1 -1 includes a large prime number p.sub.1 ' and bit lengths of p.sub.1 and p.sub.2 exceed 1/2 of the bit length of p.
The conventional prime number generating method has the following problems which is to be solved by the present invention.
(Problem 1) In the conventional prime number generating method, a composite number is generated in very low probability. PA0 (Problem 2) In the conventional method, p-1 and p+1 include large prime numbers, but besides that it is known that in the case where one of the polynomial F (p) which is a factor of p.sup.s -1 (s: arbitrary integer) such as p.sup.2 +p+1, p.sup.2 -p+1, . . . is composed of the product of only small prime numbers, the prime factors can be solved comparatively easily. Here, a number composed of the product of prime numbers not larger than integer B is called B-smooth. In other words, that F(p) is not B-smooth with respect to a small B is a measure to cope with the prime factorization utilizing F(p). However, in the conventional method, since what integer B in t-polynomial F(p) becomes B-smooth is not considered, there is such a problem that a maximum order of F(p) to which a measure is taken is not found. In order to check as to whether or not F(p) is B-smooth, F(p) is practically divided by a prime number not larger than B many times, but in the case where a judgment is made whether or not a certain F(p) is B-smooth, when B is large, prime number data become enormous and thus a lot of time is required. Namely, it takes time to judge whether or not F(p) is B-smooth, and it is very difficult to factorize an arbitrary F(p) into prime factor as long as a maximum order of F(p) to which a measure is taken is not found. Because of these, in the conventional method, the measure of the prime factorization is taken to F(p)=p-1, p+1, but the measure is not taken to F(p) of the second order or higher. PA0 (Problem 3) In the conventional prime number generating method, as for a measure against iterated-encryption attack, a method in which a large prime number p" is included in p'-1 as to a prime number p' included in p-1 is used. In this measure against the iterated-encryption attack, generation of a very weak key can be avoided, but there is a possibility that attack will be successful.
As an effective measure against the iterated-encryption attack which is conventionally known, there is the Maurer judging method (Fast generation of secure RSA-moduli with almost maximal diversity, Advances in Cryptology-EUROCRYPT '89, Lecture Notes in Computer Science, Vol.434, pp.636-647). The following simply describes the Maurer judging method.
Maurer Judging Method
As for a prime number p, the following conditions (2) are satisfied. EQU p=2h.sub.p p'+1(p'&gt;h.sub.p, p':prime number)
and EQU p'=2h.sub.p 'p"+1(p"&gt;h.sub.p ',p": prime number) (2)
In the case where p and q which satisfy these two conditions are used for secret keys of RSA and an encryption key of RSA is e, when the following condition (3) is satisfied, it is assured that the probability f that a number of repetition u of encryption required for obtaining a plain text X from a cipher text X.sup.e satisfies the following condition (4) (with respect to the plain text X) is as the following condition (5). EQU e.sup.p'-1.ident.1 (mod p') and (mod q') EQU e.sup.(p'-1)/p".notident.1 (mod p') and (mod q') (3) EQU e is a primitive element in (mod p') and (mod q') EQU u.gtoreq.min(p'-1, q'-1) (4) EQU f.gtoreq.1-l/(p'q') (5)
More specifically, in the case where n=1024 bits, p=q=512 bits and p'=q'=260 bits, it is assured that unless encryption is not repeated at least 2.sup.260 times for all the plain texts except for 2.sup.504 {=2.sup.1024.div.(2.sup.260.times.2.sup.260)} plain texts in the universal set of 2.sup.1024 plain texts, the original text cannot be obtained.
In the Maurer judging method, since the Pocklington provable prime number judging method, to be mentioned later, is carried out on a basis of the encryption key e of RSA, the Maurer judging method is a measure against the iterated-encryption attack and at the same time is a method for performing a provable prime number judgement.